package 刷题10月.动态规划;
import java.util.*;

// https://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec?tpId=188&&tqId=38556&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
public class NC7买卖股票的最好时机0929 {


    /**
     * @param prices int整型一维数组
     * @return int整型
     */
    //贪心做法 双指针
//     public int maxProfit (int[] prices) {
//         // write code here
//         int minVal=prices[0];//记录数组中访问过的最小值
//         int profit=0;//记录最大利润
//         for(int i=1;i<prices.length;i++){
//             if(prices[i]<minVal){
//                 minVal=prices[i];
//             }
//             profit=Math.max(profit,prices[i]-minVal);
//         }
//         return profit;
//     }

    //单调栈
//     public int maxProfit(int[] prices) {
//     if (prices == null || prices.length == 0)
//         return 0;
//     Stack<Integer> stack = new Stack<>();
//     stack.push(prices[0]);
//     int max = 0;
//     for (int i = 1; i < prices.length; i++) {
//         //如果栈顶元素大于prices[i]，那么栈顶元素出栈，
//         //把prices[i]压栈，要始终保证栈顶元素是最小的
//         if (stack.peek() > prices[i]) {
//             stack.pop();
//             stack.push(prices[i]);
//         } else {
//             //否则如果栈顶元素不大于prices[i]，就要计算
//             //prices[i]和栈顶元素的差值
//             max = Math.max(max, prices[i] - stack.peek());
//         }
//     }
//     return max;
// }

//     确定状态
//     找到转移公式
//     确定初始条件以及边界条件
//     计算结果 dp
    public int maxProfit(int[] prices) {
        // write code here
        int max = 0;
        int minPrice = prices[0];
        //每一天的利润最大化=前一天的利润最大化或者今天的价格减去这几天的最小值

        for (int i = 1; i < prices.length; i++) {
            minPrice = Math.min(prices[i], minPrice);
            max = Math.max(max, prices[i] - minPrice);
        }
        return max;
    }
}



